package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/7/12 10:57
 */
public class Rob_198 {

    public int rob(int[] nums) {
        int len = nums.length;
        if (len <= 1) return len == 0 ? 0 : nums[0];
        int[] cash = new int[len];
        cash[0] = nums[0];
        cash[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            // 有两种选择，一种是直接选择前一次，另一种是选隔一个加上当前的值
            cash[i] = Math.max(cash[i - 1], cash[i - 2] + nums[i]);
        }
        return cash[len - 1];
    }

    static class Solution {
        public int rob(int[] nums) {
            int len = nums.length;
            if (len <= 1) return len == 0 ? 0 : nums[0];
            // 从第二个开始也要进行选择
            int pre = nums[0], cur = Math.max(nums[0], nums[1]);
            for (int i = 2; i < len; i++) {
                int temp = Math.max(cur, pre + nums[i]);
                pre = cur;
                cur = temp;
            }
            return cur;
        }

    }

}
